Divisibility, Factors, and Multiples

Factors and Multiples: Definition

The Concept of Divisibility

The fundamental concept that underpins factors and multiples is divisibility. For any two integers, $a$ and $b$, with $b$ being a non-zero integer ($b \neq 0$), we say that $a$ is divisible by $b$ if the result of the division $a \div b$ is an exact integer, with no remainder. This relationship can be expressed mathematically as finding an integer $k$ such that $a = b \times k$.

When an integer $a$ is divisible by a non-zero integer $b$, we can describe this relationship using several terms:

• "$b$ divides $a$." This is the formal mathematical statement, often written as $b | a$.
• "$b$ is a factor of $a$."
• "$b$ is a divisor of $a$."
• "$a$ is a multiple of $b$."

If the division of $a$ by $b$ does not result in an integer (i.e., there is a non-zero remainder), we say that $a$ is not divisible by $b$, or $b$ does not divide $a$, denoted as $b \nmid a$.

Example: Let $a=15$ and $b=5$. When we divide $15$ by $5$, the result is $15 \div 5 = 3$. Since $3$ is an integer, $15$ is divisible by $5$. We can write $5 | 15$. This also means $15 = 5 \times 3$, where $k=3$ is an integer. So, $5$ is a factor of $15$, $5$ is a divisor of $15$, and $15$ is a multiple of $5$.

Example: Let $a=10$ and $b=4$. When we divide $10$ by $4$, the result is $10 \div 4 = 2.5$, which is not an integer. Using the division algorithm, $10 = 4 \times 2 + 2$ (with a remainder of 2). So, $10$ is not divisible by $4$. We write $4 \nmid 10$. $4$ is not a factor of $10$, and $10$ is not a multiple of $4$.

Divisibility is primarily discussed in the context of integers. While the formal concepts extend to other algebraic structures, in elementary mathematics, we typically focus on integers.

Factors (or Divisors)

An integer $b$ is a factor (or divisor) of an integer $a$ if $a$ is divisible by $b$. This means that when you divide $a$ by $b$, you get an integer result with no remainder.

Formally, $b$ is a factor of $a$ if and only if there exists an integer $k$ such that $a = b \times k$.

In introductory number theory, we often focus on finding the positive factors of a positive integer.

Examples of positive factors:

• To find the positive factors of $24$: We list all positive integers that divide 24 exactly.
  • $24 \div 1 = 24 \implies 1$ and $24$ are factors.
  • $24 \div 2 = 12 \implies 2$ and $12$ are factors.
  • $24 \div 3 = 8 \implies 3$ and $8$ are factors.
  • $24 \div 4 = 6 \implies 4$ and $6$ are factors.

  Since we've found all pairs of factors $(1, 24), (2, 12), (3, 8), (4, 6)$, we can stop checking once the potential factor exceeds the square root of 24 ($\sqrt{24} \approx 4.9$), as any larger factor would have a corresponding smaller factor already found. The positive factors of $24$ are $\mathbf{1, 2, 3, 4, 6, 8, 12, 24}$.

• The positive factors of $16$ are $1, 2, 4, 8, 16$. Note that 4 is listed only once even though $16 = 4 \times 4$. Factors are the divisors, not the pairs.
• A prime number (a natural number greater than 1 with exactly two distinct positive divisors) like $13$ has only two positive factors: $1$ and $13$.
• The number $1$ has only one positive factor: $1$.

Key properties of positive factors of a positive integer $n$ ($n>0$):

• The smallest positive factor of $n$ is always $1$.
• The largest positive factor of $n$ is always $n$.
• Every positive factor of $n$ is less than or equal to $n$.
• Every positive integer $n > 1$ has at least two distinct positive factors: $1$ and $n$.
• The number of positive factors of any positive integer is finite.

Note: Negative factors also exist. If $b$ is a factor of $a$, then $-b$ is also a factor of $a$. E.g., factors of 24 are $\pm 1, \pm 2, \pm 3, \pm 4, \pm 6, \pm 8, \pm 12, \pm 24$. Usually, when we say "factors" in elementary contexts, we mean positive factors.

Multiples

An integer $a$ is a multiple of an integer $b$ (where $b \neq 0$) if $a$ is divisible by $b$. This means that $a$ can be obtained by multiplying $b$ by some integer $k$.

Formally, $a$ is a multiple of $b$ if and only if there exists an integer $k$ such that $a = b \times k$.

In elementary arithmetic, we often focus on the positive multiples of a positive integer.

Examples of multiples:

• To find the multiples of $4$: We multiply 4 by any integer $k \in \mathbb{Z}$.
  • For $k=0$: $4 \times 0 = 0$. So 0 is a multiple of 4.
  • For $k=1, 2, 3, ...$: $4 \times 1 = 4, 4 \times 2 = 8, 4 \times 3 = 12, ...$. These are the positive multiples.
  • For $k=-1, -2, -3, ...$: $4 \times (-1) = -4, 4 \times (-2) = -8, 4 \times (-3) = -12, ...$. These are the negative multiples.

  The multiples of $4$ are $\mathbf{\ldots, -12, -8, -4, 0, 4, 8, 12, 16, \ldots}$. The positive multiples are $4, 8, 12, 16, \ldots$.

• The positive multiples of $10$ are obtained by multiplying 10 by $1, 2, 3, ...$: $10, 20, 30, 40, \ldots$.
• The multiples of $1$ are all integers, since any integer $a$ can be written as $1 \times a$. So, the multiples of 1 are $\ldots, -2, -1, 0, 1, 2, \ldots$.

Key properties of multiples of a non-zero integer $n$:

• $0$ is a multiple of every non-zero integer ($n \times 0 = 0$).
• Every non-zero integer $n$ is a multiple of itself ($n \times 1 = n$). It is also a multiple of $-n$ ($(-n) \times (-1) = n$).
• For a positive integer $n$, the smallest positive multiple is $n$ itself ($n \times 1$).
• For a positive integer $n$, the positive multiples are always greater than or equal to $n$.
• There are infinitely many multiples of any non-zero integer (positive and negative).

The Interdependence of Factors and Multiples

The concepts of factors and multiples describe the same mathematical relationship from two different perspectives. They are directly related through divisibility:

• If $a$ is a multiple of $b$ (where $b \neq 0$), then $b$ is a factor (or divisor) of $a$. (Because if $a = bk$, then $a/b = k$, an integer).
• If $b$ is a factor (or divisor) of $a$ (where $b \neq 0$), then $a$ is a multiple of $b$. (Because if $a/b = k$ where $k$ is an integer, then $a = bk$).

Example: Since $24$ is a multiple of $6$ ($24 = 6 \times 4$), it means $6$ is a factor of $24$. Conversely, since $5$ is a factor of $35$ ($35 \div 5 = 7$), it means $35$ is a multiple of $5$.

Understanding this inverse relationship is fundamental to working with concepts like prime factorization, GCD, and LCM.

Divisibility Tests

Divisibility tests are a set of convenient rules or shortcuts that allow us to quickly determine whether one integer is divisible by another integer without performing the complete long division. These tests are derived from the properties of our base-10 number system and the general properties of divisibility. They are invaluable tools for finding factors of numbers, simplifying fractions, determining if a number is prime, and working with prime factorization.

These tests are typically applied to check the divisibility of a whole number by a small integer divisor.

Detailed Divisibility Tests for Small Integers

Here are some common divisibility tests for integers:

• Divisibility by 2:

  An integer is divisible by $2$ if and only if its last digit (the digit in the ones place) is an even digit, i.e., $0, 2, 4, 6,$ or $8$.

  Explanation: Any whole number can be expressed as $10a + b$, where $b$ is the last digit and $a$ represents the number formed by the remaining digits to the left of the ones place multiplied by the appropriate power of 10. For example, $4572 = 457 \times 10 + 2$. Since $10$ is divisible by $2$, any multiple of $10$ ($10a$) is also divisible by $2$. Therefore, the divisibility of the entire number ($10a+b$) by $2$ depends solely on the divisibility of its last digit ($b$) by $2$.

  Example: $4572$. The last digit is $2$, which is an even digit. So $4572$ is divisible by $2$ ($4572 \div 2 = 2286$).

  Example: $905$. The last digit is $5$, which is an odd digit. So $905$ is not divisible by $2$.

• Divisibility by 3:

  An integer is divisible by $3$ if and only if the sum of its digits is divisible by $3$.

  Explanation: This test is based on the property that any positive integer is congruent to the sum of its digits modulo $3$. This is because powers of $10$ leave a remainder of $1$ when divided by $3$ ($10 \equiv 1 \pmod{3}$, $100 = 10^2 \equiv 1^2 = 1 \pmod{3}$, $10^n \equiv 1 \pmod{3}$). If a number is $d_n 10^n + \dots + d_1 10^1 + d_0 10^0$, its value modulo 3 is equivalent to $d_n(1) + \dots + d_1(1) + d_0(1) \pmod{3}$, which is the sum of its digits.

  Example: $729$. The sum of its digits is $7+2+9 = 18$. $18$ is divisible by $3$ ($18 \div 3 = 6$). So, $729$ is divisible by $3$ ($729 \div 3 = 243$).

  Example: $514$. The sum of its digits is $5+1+4 = 10$. $10$ is not divisible by $3$. So, $514$ is not divisible by $3$.

• Divisibility by 4:

  An integer is divisible by $4$ if and only if the number formed by its last two digits is divisible by $4$.

  Explanation: This test works because $100$ is divisible by $4$ ($100 = 4 \times 25$). Any number with 3 or more digits can be written in the form $100a + b$, where $b$ is the number formed by the last two digits. For example, $3456 = 34 \times 100 + 56$. Since $100a$ is always divisible by $4$, the divisibility of the entire number by $4$ depends only on the divisibility of the number formed by its last two digits ($b$) by $4$.

  Example: $3456$. The number formed by the last two digits is $56$. $56$ is divisible by $4$ ($56 \div 4 = 14$). So, $3456$ is divisible by $4$ ($3456 \div 4 = 864$).

  Example: $9170$. The number formed by the last two digits is $70$. $70$ is not divisible by $4$ ($70 \div 4 = 17$ with remainder $2$). So, $9170$ is not divisible by $4$.

• Divisibility by 5:

  An integer is divisible by $5$ if and only if its last digit is $0$ or $5$.

  Explanation: Similar to the test for 2, this is because 10 is divisible by 5. Any number $10a + b$ is divisible by 5 if and only if its last digit $b$ is divisible by 5. The only digits divisible by 5 are 0 and 5.

  Example: $870$ is divisible by $5$ (last digit is $0$). $135$ is divisible by $5$ (last digit is $5$). $998$ is not divisible by $5$ (last digit is neither $0$ nor $5$).

• Divisibility by 6:

  An integer is divisible by $6$ if and only if it is divisible by both $2$ and $3$.

  Explanation: This rule works because $2$ and $3$ are the prime factors of $6$, and they are relatively prime (their Greatest Common Divisor is $1$). If a number is a multiple of both 2 and 3, it must be a multiple of their product, $2 \times 3 = 6$. (This is property 10 from the previous section on divisibility properties).

  Example: $108$. Last digit is $8$ (even), so it's divisible by $2$. The sum of digits is $1+0+8 = 9$. $9$ is divisible by $3$. Since $108$ is divisible by both $2$ and $3$, it is divisible by $6$ ($108 \div 6 = 18$).

  Example: $234$. Last digit is $4$ (even), so it's divisible by $2$. The sum of digits is $2+3+4 = 9$. $9$ is divisible by $3$. Since $234$ is divisible by both $2$ and $3$, it is divisible by $6$ ($234 \div 6 = 39$).

  Example: $30$. Last digit is $0$ (even), divisible by $2$. Sum of digits is $3$, divisible by $3$. Thus, divisible by $6$.

• Divisibility by 8:

  An integer is divisible by $8$ if and only if the number formed by its last three digits is divisible by $8$.

  Explanation: Similar to the test for 4, this test works because $1000$ is divisible by $8$ ($1000 = 8 \times 125$). Any number with 4 or more digits can be written as $1000a + b$, where $b$ is the number formed by the last three digits. Since $1000a$ is always divisible by $8$, the divisibility of the entire number by $8$ depends only on the divisibility of the number formed by its last three digits ($b$) by $8$.

  Example: $567120$. The number formed by the last three digits is $120$. $120 \div 8 = 15$. So, $120$ is divisible by $8$. Thus, $567120$ is divisible by $8$ ($567120 \div 8 = 70890$).

  Example: $204$. The number formed by the last three digits is $204$. $204 \div 8 = 25$ with remainder $4$. So, $204$ is not divisible by $8$.

• Divisibility by 9:

  An integer is divisible by $9$ if and only if the sum of its digits is divisible by $9$.

  Explanation: This test is based on the property that any positive integer is congruent to the sum of its digits modulo $9$. This is because powers of $10$ leave a remainder of $1$ when divided by $9$ ($10 \equiv 1 \pmod{9}$, $100 \equiv 1 \pmod{9}$, $10^n \equiv 1 \pmod{9}$). The sum of the digits property for divisibility by 9 is a stronger version of the test for 3.

  Example: $819$. The sum of its digits is $8+1+9 = 18$. $18$ is divisible by $9$ ($18 \div 9 = 2$). So, $819$ is divisible by $9$ ($819 \div 9 = 91$).

  Example: $345$. The sum of its digits is $3+4+5 = 12$. $12$ is not divisible by $9$. So, $345$ is not divisible by $9$.

  Note: If a number is divisible by 9, it is automatically divisible by 3. However, if a number is divisible by 3, it is not necessarily divisible by 9 (e.g., 6 is divisible by 3 but not 9; sum of digits is 6).

• Divisibility by 10:

  An integer is divisible by $10$ if and only if its last digit is $0$.

  Explanation: This is the simplest test and follows directly from the base-10 place value system. Any number ending in 0 is a multiple of 10.

  Example: $1230$ is divisible by $10$ (last digit is $0$). $1235$ is not (last digit is $5$).

• Divisibility by 11:

  An integer is divisible by $11$ if and only if the alternating sum of its digits is divisible by $11$. To calculate the alternating sum, start from the rightmost digit (ones place) and proceed to the left, adding the digits at odd positions (1st, 3rd, 5th, ...) and subtracting the digits at even positions (2nd, 4th, 6th, ...).

  Explanation: This test is based on powers of $10$ modulo $11$. $10 \equiv -1 \pmod{11}$, $100 \equiv (-1)^2 = 1 \pmod{11}$, $1000 \equiv (-1)^3 = -1 \pmod{11}$, and so on. The value of a number $d_n 10^n + \dots + d_1 10^1 + d_0 10^0$ modulo 11 is $d_n (\pm 1) + \dots - d_1 + d_0 \pmod{11}$, depending on the position. Grouping by parity of position gives the alternating sum $d_0 - d_1 + d_2 - d_3 + \dots$.

  Example: $121$. Alternating sum from right: $1 - 2 + 1 = 0$. $0$ is divisible by $11$. So $121$ is divisible by $11$ ($121 \div 11 = 11$).

  Example: $1331$. Alternating sum from right: $1 - 3 + 3 - 1 = 0$. $0$ is divisible by $11$. So $1331$ is divisible by $11$ ($1331 \div 11 = 121$).

  Example: $9879$. Alternating sum from right: $9 - 7 + 8 - 9 = 2 + 8 - 9 = 10 - 9 = 1$. $1$ is not divisible by $11$. So $9879$ is not divisible by $11$.

  Example: $18051$. Alternating sum from right: $1 - 5 + 0 - 8 + 1 = -4 - 8 + 1 = -12 + 1 = -11$. $-11$ is divisible by $11$. So $18051$ is divisible by $11$ ($18051 \div 11 = 1641$).

• Divisibility by 12:

  An integer is divisible by $12$ if and only if it is divisible by both $3$ and $4$. (This works because $3$ and $4$ are relatively prime factors of $12$).

  Example: $216$. Sum of digits $= 2+1+6 = 9$. $9$ is divisible by $3$. The number formed by the last two digits is $16$. $16$ is divisible by $4$ ($16 \div 4 = 4$). Since $216$ is divisible by both $3$ and $4$, it is divisible by $12$ ($216 \div 12 = 18$).

  Example: $130$. Last digit is 0, divisible by 2 (but we need test for 4). Last two digits form 30. 30 is not divisible by 4. Sum of digits is 4, not divisible by 3. So 130 is not divisible by 12.

These divisibility tests are powerful tools for analyzing numbers, especially when dealing with factorization or simplifying expressions.

Prime and Composite Numbers

Positive integers greater than $1$ are classified into two important and mutually exclusive categories based on the number of positive factors they have: prime numbers and composite numbers. This classification is fundamental in number theory and forms the basis for concepts like factorization and the study of properties of integers.

Prime Numbers

A prime number is a natural number greater than $1$ that has exactly two distinct positive factors (or divisors): the number $1$ and the number itself.

In other words, a prime number $p$ can only be divided evenly by 1 and $p$.

Let's identify the positive factors for some numbers greater than 1:

• For the number 2: The positive numbers that divide 2 evenly are 1 and 2. There are exactly two distinct positive factors (1 and 2). Hence, 2 is a prime number.
• For the number 3: The positive numbers that divide 3 evenly are 1 and 3. There are exactly two distinct positive factors (1 and 3). Hence, 3 is a prime number.
• For the number 4: The positive numbers that divide 4 evenly are 1, 2, and 4. There are three distinct positive factors (1, 2, and 4). Hence, 4 is not a prime number.
• For the number 5: The positive numbers that divide 5 evenly are 1 and 5. There are exactly two distinct positive factors (1 and 5). Hence, 5 is a prime number.
• For the number 6: The positive numbers that divide 6 evenly are 1, 2, 3, and 6. There are four distinct positive factors (1, 2, 3, and 6). Hence, 6 is not a prime number.
• For the number 7: The positive numbers that divide 7 evenly are 1 and 7. There are exactly two distinct positive factors (1 and 7). Hence, 7 is a prime number.

The sequence of prime numbers begins with $\mathbf{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, ...}$

Important facts about prime numbers:

• The number 2 is unique among prime numbers. It is the smallest prime number and the only even prime number. All other even numbers greater than 2 are divisible by 2, 1, and themselves, thus having at least three factors.
• There are infinitely many prime numbers. This significant result was proven by the ancient Greek mathematician Euclid around 300 BC.

Composite Numbers

A composite number is a natural number greater than $1$ that is not a prime number. By definition, a composite number is a natural number greater than 1 that has more than two distinct positive factors.

In other words, a composite number $n$ can be divided evenly by at least one positive integer other than 1 and $n$. This means a composite number can be expressed as a product of two smaller natural numbers (each greater than 1).

Examples of composite numbers:

• 4: Factors are {1, 2, 4}. (More than two factors). $4 = 2 \times 2$.
• 6: Factors are {1, 2, 3, 6}. (More than two factors). $6 = 2 \times 3$.
• 8: Factors are {1, 2, 4, 8}. (More than two factors). $8 = 2 \times 4$ or $2 \times 2 \times 2$.
• 9: Factors are {1, 3, 9}. (More than two factors). $9 = 3 \times 3$.
• 10: Factors are {1, 2, 5, 10}. (More than two factors). $10 = 2 \times 5$.
• 12: Factors are {1, 2, 3, 4, 6, 12}. (More than two factors). $12 = 2 \times 6$ or $3 \times 4$ or $2 \times 2 \times 3$.

The sequence of composite numbers begins with $\mathbf{4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, ...}$

The Special Status of the Number 1

The natural number $1$ is unique and holds a special status in number theory. It is neither a prime number nor a composite number. This is because its definition does not fit either category:

• A prime number must have exactly two distinct positive factors. The number 1 has only one positive factor (which is 1 itself).
• A composite number must have more than two distinct positive factors. The number 1 has only one positive factor.

Thus, the set of natural numbers greater than 1 is completely partitioned into the set of prime numbers and the set of composite numbers. The number 1 stands alone.

The Fundamental Theorem of Arithmetic

This is a cornerstone theorem in number theory that highlights the central role of prime numbers. It states that every integer greater than $1$ can be uniquely expressed as a product of prime numbers.

Statement: Every integer greater than $1$ is either a prime number itself or can be uniquely expressed as a product of prime numbers, regardless of the order of the prime factors.

This theorem means that prime numbers are the multiplicative building blocks for all integers greater than 1. Any composite number can be broken down into a specific set of prime factors, and this set (including the number of times each prime appears) is unique for that number. The process of finding this prime factorization is called prime factorization.

Example: The composite number $20$ can be uniquely written as a product of primes: $20 = 2 \times 2 \times 5 = 2^2 \times 5^1$. The prime factors are 2 (appearing twice) and 5 (appearing once). No other combination of prime numbers will multiply to 20.

Example: The composite number $42$ can be uniquely written as $42 = 2 \times 3 \times 7$. The prime factors are 2, 3, and 7, each appearing once.

Example: The prime number $7$ is itself a prime, and its prime factorization is simply $7^1$.

The fundamental theorem of arithmetic is crucial for many concepts, including finding the Greatest Common Divisor (GCD) and the Least Common Multiple (LCM) of numbers, simplifying fractions, and in cryptography.

Determining if a Number is Prime

To determine whether a given integer $n$ greater than $1$ is a prime number or a composite number, we need to check if it has any positive factors other than the two trivial factors: $1$ and $n$ itself. If we find any such factor, the number $n$ is composite. If, after checking systematically, we find no such factor, then its only positive factors are $1$ and $n$, and the number $n$ is prime.

The most direct way to do this is to test for divisibility by every integer starting from $2$ up to $n-1$. However, this method is highly inefficient, especially for larger numbers. Fortunately, we can significantly optimize the process using mathematical properties.

Optimized Methods for Primality Testing

Instead of testing all integers up to $n-1$, we can dramatically reduce the range of numbers we need to check for divisibility.

Optimization Principle: If an integer $n > 1$ is composite, it must have at least one positive factor $d$ such that $1 < d \le \sqrt{n}$.

Proof of the Principle:

Let $n$ be a composite number such that $n > 1$. By definition, $n$ has at least one positive factor other than $1$ and $n$. Let $d$ be any positive factor of $n$ such that $d \neq 1$ and $d \neq n$. Since $d$ is a factor of $n$, there exists another factor $k$ such that $n = d \times k$. Because $d \neq 1$ and $d \neq n$, it must be that $k \neq n$ and $k \neq 1$. So, both $d > 1$ and $k > 1$.

Now consider the relationship between $d$ and $k$. There are three possibilities:

• Case 1: $d = k$. If $d = k$, then $n = d \times d = d^2$. This means $n$ is a perfect square, and $d = \sqrt{n}$. In this case, we have found a factor $d$ such that $d = \sqrt{n}$, which satisfies $d \le \sqrt{n}$.
• Case 2: $d < k$. If $d < k$, multiply both sides of the inequality by $d$ (since $d > 0$): $d \times d < d \times k$. So, $d^2 < n$. Taking the positive square root of both sides (since $d > 0$ and $n > 0$): $\sqrt{d^2} < \sqrt{n}$, which means $d < \sqrt{n}$. In this case, we have found a factor $d$ such that $1 < d < \sqrt{n}$, which satisfies $d \le \sqrt{n}$.
• Case 3: $d > k$. If $d > k$, multiply both sides of the inequality by $k$ (since $k > 0$): $d \times k > k \times k$. So, $n > k^2$. Taking the positive square root of both sides (since $n > 0$ and $k > 0$): $\sqrt{n} > \sqrt{k^2}$, which means $\sqrt{n} > k$, or $k < \sqrt{n}$. In this case, we have found a factor $k$ such that $1 < k < \sqrt{n}$, which satisfies $k \le \sqrt{n}$.

In every case where $n$ is composite, we have shown that there must exist at least one positive factor (other than 1 and $n$) that is less than or equal to $\sqrt{n}$.

Therefore, to check if $n$ is prime, we only need to test for divisibility by integers starting from $2$ up to $\lfloor \sqrt{n} \rfloor$, where $\lfloor \sqrt{n} \rfloor$ is the greatest integer less than or equal to the square root of $n$. If $n$ is not divisible by any integer in this range, it cannot have any factor greater than $\sqrt{n}$ either (because if it did, say factor $f > \sqrt{n}$, then $n/f$ would be a factor less than $\sqrt{n}$, and we would have found it). Thus, if $n$ has no factors in the range $[2, \lfloor \sqrt{n} \rfloor]$, its only positive factors must be $1$ and $n$, making it prime.

Further Optimization: We only need to test for divisibility by prime numbers up to $\lfloor \sqrt{n} \rfloor$. This is because if $n$ is divisible by a composite number $c$ where $1 < c \le \sqrt{n}$, then $c$ must have at least one prime factor $p$. This prime factor $p$ must be less than or equal to $c$ (since $p \le c$). Since $c$ is a factor of $n$ and $p$ is a factor of $c$, $p$ must also be a factor of $n$ (by the transitive property of divisibility). Thus, if $n$ has any composite factor $\le \sqrt{n}$, it must also have a prime factor $\le \sqrt{n}$. So, checking only prime divisors up to $\sqrt{n}$ is sufficient.

Practical Algorithm for Primality Testing

Given an integer $n > 1$, we can determine if it's prime using the optimized method:

1. Handle the smallest prime: If $n = 2$, then $n$ is prime.
2. Handle even numbers: If $n$ is an even number and $n > 2$, then $n$ is composite (since it is divisible by 2).
3. If $n$ is an odd number:
   • Calculate the integer part of the square root of $n$. Let $L = \lfloor \sqrt{n} \rfloor$.
   • Test for divisibility of $n$ by all odd integers starting from $3$ up to $L$. (Testing only prime numbers in this range is more efficient if a list of primes is available, but testing all odd numbers is simpler to implement if you don't have a list of primes).
   • If $n$ is divisible by any of these odd integers, then $n$ is composite.
   • If $n$ is not divisible by any of these odd integers up to $L$, then $n$ is prime.

Answer:

Answer:

This optimized method significantly reduces the number of divisions needed to check for primality, making it practical for testing smaller integers. For very large numbers (used in cryptography, for example), much more sophisticated and complex primality tests are employed.

Prime Factorisation

Prime factorization is the process of decomposing a composite number into a product of its prime numbers. The set of prime numbers that multiply together to form the original number is unique for every composite number greater than 1. This uniqueness is guaranteed by the Fundamental Theorem of Arithmetic (also known as the Unique Factorization Theorem).

The result of prime factorization is typically written as a product of prime numbers raised to their respective powers (e.g., $2^3 \times 3^2$).

Prime factorization is a cornerstone concept in number theory, providing a foundational tool for solving various problems.

Methods for Finding Prime Factorization

The goal is to find the unique set of prime numbers (with their multiplicities) that, when multiplied together, equal the given composite number.

Method 1: Factor Tree

A factor tree is a visual method to find the prime factors of a composite number. You start with the given number at the top and repeatedly break it down into pairs of factors. You continue factoring any composite factors until all the numbers at the ends of the branches are prime numbers. The prime factors are typically circled to indicate that you cannot factor them further.

Answer:

Start with 72 at the top. Choose any pair of factors whose product is 72. For example, we can choose 8 and 9.

(Note: The image shows the number 72 at the top, branching down to 8 and 9. 8 branches down to 2 and 4. 9 branches down to 3 and 3 (3s are circled as they are prime). 4 branches down to 2 and 2 (2s are circled as they are prime). The numbers 2, 2, 2, 3, 3 are at the ends of the branches and are prime).

The prime factors identified at the end of the branches are $2, 2, 2, 3, 3$.

The prime factorization of $72$ is $2 \times 2 \times 2 \times 3 \times 3$.

Writing this in exponential form (collecting identical factors): $2^3 \times 3^2$.

The factor tree can be drawn differently depending on the initial factors chosen (e.g., starting with $2 \times 36$), but the set of prime factors at the bottom will always be the same (three 2s and two 3s), illustrating the uniqueness stated by the Fundamental Theorem of Arithmetic.

Method 2: Division Method (Repeated Division by Prime Factors)

This is a more systematic method, especially efficient for larger numbers. It involves repeatedly dividing the number by the smallest possible prime factor until the quotient becomes 1.

Steps:

1. Write the number to be factorized. Draw a vertical line to its right.
2. Find the smallest prime number that divides the current number exactly. Write this prime number to the left of the vertical line.
3. Write the quotient (the result of the division) below the current number, to the right of the vertical line.
4. Repeat steps 2 and 3 with the new quotient as the number to be divided. Continue this process until the quotient obtained is 1.
5. The prime factors of the original number are all the prime numbers listed to the left of the vertical line.

Answer:

Answer:

Uses and Applications of Prime Factorization

Prime factorization is a foundational concept with numerous applications in number theory and other areas of mathematics:

• Finding the Greatest Common Divisor (GCD): The GCD of two or more numbers is the product of all the prime factors they have in common, where each common prime factor is raised to the lowest power it appears in any of the individual prime factorizations.

  Example: Find GCD$(12, 18)$. Prime factorization of $12 = 2^2 \times 3^1$. Prime factorization of $18 = 2^1 \times 3^2$. Common prime factors are 2 and 3. Lowest power of 2 is $2^1$. Lowest power of 3 is $3^1$. GCD$(12, 18) = 2^1 \times 3^1 = 2 \times 3 = 6$.

• Finding the Least Common Multiple (LCM): The LCM of two or more numbers is the product of all the prime factors that appear in any of the individual prime factorizations, where each prime factor is raised to the highest power it appears in any of the factorizations.

  Example: Find LCM$(12, 18)$. Prime factorization of $12 = 2^2 \times 3^1$. Prime factorization of $18 = 2^1 \times 3^2$. The primes involved are 2 and 3. Highest power of 2 is $2^2$. Highest power of 3 is $3^2$. LCM$(12, 18) = 2^2 \times 3^2 = 4 \times 9 = 36$.

• Simplifying Radicals (Square Roots, Cube Roots, etc.): Prime factorization helps in simplifying radicals by identifying perfect square (or cube, etc.) factors within the number under the radical sign.

  Example: Simplify $\sqrt{50}$. Prime factorization of $50 = 2 \times 5 \times 5 = 2 \times 5^2$. $\sqrt{50} = \sqrt{2 \times 5^2} = \sqrt{2} \times \sqrt{5^2} = \sqrt{2} \times 5 = 5\sqrt{2}$.

• Simplifying Fractions: To reduce a fraction to its lowest terms, find the prime factorization of the numerator and the denominator and cancel out the common prime factors (each raised to the minimum of the powers they appear in the numerator and denominator).

  Example: Simplify $\frac{24}{36}$. Prime factorization of $24 = 2^3 \times 3^1$. Prime factorization of $36 = 2^2 \times 3^2$.

  $\quad \frac{24}{36} = \frac{2^3 \times 3^1}{2^2 \times 3^2} = \frac{\cancel{2^2} \times 2 \times \cancel{3^1}}{\cancel{2^2} \times \cancel{3^1} \times 3} = \frac{2}{3}$

  Alternatively, think of canceling the common factors: two 2s and one 3.

Prime factorization is a very powerful tool that underpins many other concepts and techniques in number theory and algebra, making it a core skill in mathematics.